#include <iostream>
#include <string>
using namespace std;


/**
  * @方法: 迭代
  * @时间复杂度: o()
  * @空间复杂度: o()
  * @评价:
*/
int longestCommonSubsequence(string text1, string text2) {
    int dp[1005][1005];
    for(int i=0;i<=text1.length();i++) dp[i][0] = 0;
    for(int j=0;j<=text2.length();j++) dp[0][j] = 0;

    for(int i=1;i<=text1.length();i++){
        for(int j=1;j<=text2.length();j++){
            if(text1[i-1] == text2[j-1]) dp[i][j] = 1 + dp[i-1][j-1];
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[text1.length()][text2.length()];
}


/**
  * @方法: 带记忆的递归
  * @时间复杂度: o()
  * @空间复杂度: o()
  * @评价:
*/
int memo[1005][1005];

int dp(string& text1, int i, string& text2, int j) {
    if (memo[i][j] != -1) return memo[i][j];

    if (i == text1.length() || j == text2.length()) {
        memo[i][j] = 0;
        return 0;
    }

    if (text1[i] == text2[j]) {
        memo[i][j] = 1 + dp(text1, i + 1, text2, j + 1);
        return memo[i][j];
    }

    int m = dp(text1, i + 1, text2, j);
    int n = dp(text1, i, text2, j + 1);

    memo[i][j] = max(m, n);
    return memo[i][j];
}

int longestCommonSubsequence(string text1, string text2) {
    for (int i = 0; i < 1005; i++) {
        for (int j = 0; j < 1005; j++) {
            memo[i][j] = -1;
        }
    }
    return dp(text1, 0, text2, 0);
}
